﻿/**************************************************************
 * 
 * Copyright © WMSigner Team <www.wmsigner.com> 2007-2008
 * Copyright © Dmitry Kukushkin <codecity@gmail.com> 2007-2008
 * All Rights Reserved
 * 
 **************************************************************/

using System;

namespace WebMoney.Cryptography
{
    internal static class ArithmeticKernel
    {
        private const int BITS = 32;

        public static int Significance(uint[] value)
        {
            int length = value.Length;

            while (length > 1 && value[length - 1] == 0)
                length--;

            return length;
        }

        public static int Significance(ushort[] value)
        {
            int length = value.Length;

            while (length > 1 && value[length - 1] == 0)
                length--;

            return length;
        }

        public static void Normalize(ref uint[] value)
        {
            int length = Significance(value);

            if (value.Length != length)
                Array.Resize(ref value, length);
        }

        public static void Normalize(ref ushort[] value)
        {
            int length = Significance(value);

            if (value.Length != length)
                Array.Resize(ref value, length);
        }

        public static int GetBitsCount(uint[] value)
        {
            int len = Significance(value);

            int bits = 0;
            uint temp = value[len - 1];

            while (temp > 0)
            {
                bits++;
                temp = temp >> 1;
            }

            return (len - 1) * BITS + bits;
        }

        public static int Compare(uint[] lhs, uint[] rhs)
        {
            int lhsLen = Significance(lhs);
            int rhsLen = Significance(rhs);

            if (lhsLen > rhsLen)
                return 1;
            else if (lhsLen < rhsLen)
                return -1;
            else
            {
                for (int pos = lhsLen - 1; pos >= 0; pos--)
                {
                    if (lhs[pos] > rhs[pos])
                        return 1;
                    else if (lhs[pos] < rhs[pos])
                        return -1;
                }

                return 0;
            }
        }

        public static void Sub(ref uint[] lhs, uint[] rhs)
        {
            int pos = 0;
            int borrow = 0;

            for (; pos < rhs.Length; pos++)
            {
                ulong temp = (ulong) lhs[pos] - rhs[pos] - (ulong) borrow;
                lhs[pos] = unchecked((uint) temp);
                borrow = (((temp & (1UL << BITS)) != 0) ? 1 : 0);
            }

            if (rhs.Length < lhs.Length)
                for (; pos < lhs.Length; pos++)
                {
                    ulong temp = (ulong)lhs[pos] - (ulong)borrow;
                    lhs[pos] = unchecked((uint)temp);
                    borrow = (((temp & (1UL << BITS)) != 0) ? 1 : 0);
                }

            if (1 == borrow)
                throw new ArgumentOutOfRangeException("rhs");
        }

        private static uint[] Shift(uint[] lhs, int rhs)
        {
            int shiftBits = (rhs > 0 ? rhs : -rhs) % BITS;
            int shiftWords = (rhs > 0 ? rhs : -rhs) / BITS;

            int inBitsCount = GetBitsCount(lhs);
            int inWordsCount = inBitsCount / BITS + (inBitsCount % BITS > 0 ? 1 : 0);

            int outBitsCount = inBitsCount + rhs;
            int outWordsCount = outBitsCount / BITS + (outBitsCount % BITS > 0 ? 1 : 0);

            if (outWordsCount <= 0)
                return new uint[]{ 0 };

            uint[] result = new uint[inWordsCount > outWordsCount ? inWordsCount : outWordsCount];

            if (rhs > 0)
            {
                if (0 == shiftBits)
                    Array.Copy(lhs, 0, result, shiftWords, outWordsCount - shiftWords);
                else
                {
                    int pos = 0;
                    uint carry = 0;

                    for (; pos < inWordsCount; pos++)
                    {
                        uint temp = lhs[pos];

                        result[pos + shiftWords] = (temp << shiftBits) | carry;
                        carry = temp >> (BITS - shiftBits);
                    }

                    if (pos + shiftWords < outWordsCount)
                        result[pos + shiftWords] |= carry;
                }
            }
            else
            {
                if (0 == shiftBits)
                    Array.Copy(lhs, shiftWords, result, 0, outWordsCount);
                else
                {
                    uint carry = 0;
                    int pos = outWordsCount;

                    if (pos + shiftWords < inWordsCount)
                        carry = lhs[pos + shiftWords] << (BITS - shiftBits);

                    pos--;

                    for (; pos >= 0; pos--)
                    {
                        uint temp = lhs[pos + shiftWords];

                        result[pos] = (temp >> shiftBits) | carry;
                        carry = temp << (BITS - shiftBits);
                    }
                }
            }

            return result;
        }

        public static void ShiftRight(ref uint[] value)
        {
            int len = Significance(value);

            uint carry = 0;

            for (int pos = len - 1; pos >= 0; pos--)
            {
                uint temp = value[pos];

                uint nextCarry = (temp & 1) << (BITS - 1);
                value[pos] = (temp >> 1) | carry;
                carry = nextCarry;
            }
        }

        public static void Remainder(ref uint[] lhs, uint[] rhs)
        {
            int lhsBitsCount = GetBitsCount(lhs);
            int rhsBitsCount = GetBitsCount(rhs);

            int shift = lhsBitsCount - rhsBitsCount;

            uint[] temp = Shift(rhs, shift);

            if (Compare(lhs, temp) < 0)
                ShiftRight(ref temp);

            while (Compare(lhs, rhs) > 0)
            {
                while (Compare(lhs, temp) > 0)
                    Sub(ref lhs, temp);

                lhsBitsCount = GetBitsCount(lhs);
                shift = lhsBitsCount - rhsBitsCount;

                temp = Shift(rhs, shift);

                if (Compare(lhs, temp) < 0)
                    ShiftRight(ref temp);
            }
        }
    }
}